基点|精力_Go基础加密算法和数据结构

篇首语：本文由编程笔记#小编为大家整理，主要介绍了Go基础加密算法和数据结构相关的知识，希望对你有一定的参考价值。

文章目录

• 一、加密算法
• • 1. 对称加密
  • 2. 非对称加密
  • 3. 哈希算法
  
  
• 二、数据结构与算法
• • 1. 链表
  • 2. 栈
  • 3. 堆
  • 4. Trie树
  
  

1. 对称加密

加密过程的每一步都是可逆的
加密和解密用的是同一组密钥
异或是最简单的对称加密算法

// XOR 异或运算&＃xff0c;要求plain和key的长度相同
func XOR(plain string, key []byte) string
bPlain :&＃61; []byte(plain)
bCipher :&＃61; make([]byte, len(key))
for i, k :&＃61; range key
bCipher[i] &＃61; k ^ bPlain[i]

cipher :&＃61; string(bCipher)
return cipher



DES&＃xff08;Data Encryption Standard&＃xff09;数据加密标准&＃xff0c;是目前最为流行的加密算法之一
对原始数据&＃xff08;明文&＃xff09;进行分组&＃xff0c;每组64位&＃xff0c;最后一组不足64位时按一定规则填充&＃xff0c;每一组上单独施加DES算法
DES子密钥生成
初始密钥64位&＃xff0c;实际有效位56位&＃xff0c;每隔7位有一个校验位&＃xff0c;根据初始密钥生成16个48位的子密钥

N取值从1到16&＃xff0c;N和x有固定的映射表

DES加密过程

L1, R1 &＃61; f(L0, R0, K1)&＃xff0c;依此循环&＃xff0c;得到L16和R16
S盒替换&＃xff0c;输入48位&＃xff0c;输出32位&＃xff0c;各分为8组&＃xff0c;输入每组6位&＃xff0c;输出每组4位&＃xff0c;分别在每组上施加S盒替换&＃xff0c;一共8个S盒

CBC加密过程

分组模式&＃xff0c;CBC&＃xff08;Cipher Block Chaining &＃xff09;密文分组链接模式&＃xff0c;将当前明文分组与前一个密文分组进行异或运算&＃xff0c;然后再进行加密
其他分组模式还有ECB, CTR, CFR, OFB

func DesEncryptCBC(text string, key []byte) (string, error)
src :&＃61; []byte(text)
block, err :&＃61; des.NewCipher(key) // 用des创建一个加密器cipher
if err !&＃61; nil
return "", err

blockSize :&＃61; block.BlockSize() // 分组的大小&＃xff0c;blockSize&＃61;8
src &＃61; common.ZeroPadding(src, blockSize) // 填充
out :&＃61; make([]byte, len(src)) // 密文和明文的长度一致
encrypter :&＃61; cipher.NewCBCEncrypter(block, key) // CBC分组模式加密
encrypter.CryptBlocks(out, src)
return hex.EncodeToString(out), nil

func DesDecryptCBC(text string, key []byte) (string, error)
src, err :&＃61; hex.DecodeString(text) // 转成[]byte
if err !&＃61; nil
return "", err

block, err :&＃61; des.NewCipher(key)
if err !&＃61; nil
return "", err


out :&＃61; make([]byte, len(src)) // 密文和明文的长度一致
encrypter :&＃61; cipher.NewCBCDecrypter(block, key) // CBC分组模式解密
encrypter.CryptBlocks(out, src)
out &＃61; common.ZeroUnPadding(out) // 反填充
return string(out), nil



AES&＃xff08;Advanced Encryption Standard&＃xff09;高级加密标准&＃xff0c;旨在取代DES

2. 非对称加密

• 使用公钥加密&＃xff0c;使用私钥解密
• 公钥和私钥不同
• 公钥可以公布给所有人
• 私钥只有自己保存
• 相比于对称加密&＃xff0c;运算速度非常慢

对称加密和非对称加密结合使用的案例&＃xff1a;
小明要给小红传输机密文件&＃xff0c;他俩先交换各自的公钥&＃xff0c;然后&＃xff1a;

• 小明生成一个随机的AES口令&＃xff0c;然后用小红的公钥通过RSA加密这个口令&＃xff0c;并发给小红
• 小红用自己的RSA私钥解密得到AES口令
• 双方使用这个共享的AES口令用AES加密通信

RSA是三个发明人名字的缩写&＃xff1a;Ron Rivest&＃xff0c;Adi Shamir&＃xff0c;Leonard Adleman&＃xff0c;密钥越长&＃xff0c;越难破解&＃xff0c;目前768位的密钥还无法破解&＃xff08;至少没人公开宣布&＃xff09;&＃xff0c;因此可以认为1024位的RSA密钥基本安全&＃xff0c;2048位的密钥极其安全&＃xff0c;RSA的算法原理主要用到了数论
RSA加密过程&＃xff1a;

• 随机选择两个不相等的质数p和q&＃xff1a;p&＃61;61, q&＃61;53
• 计算p和q的乘积n&＃xff1a;n&＃61;3233
• 计算n的欧拉函数φ(n) &＃61; (p-1)(q-1)&＃xff1a; φ(n) &＃61;3120
• 随机选择一个整数e&＃xff0c;使得1
• 计算e对于φ(n)的模反元素d&＃xff0c;即求解e*d&＃43; φ(n)*y&＃61;1&＃xff1a;d&＃61;2753, y&＃61;-15
• 将n和e封装成公钥&＃xff0c;n和d封装成私钥&＃xff1a;公钥&＃61;(3233&＃xff0c;17)&＃xff0c;公钥&＃61;(3233&＃xff0c;2753)

// RSA加密
func RsaEncrypt(origData []byte) ([]byte, error)
// 解密pem格式的公钥
block, _ :&＃61; pem.Decode(publicKey)
if block &＃61;&＃61; nil
return nil, errors.New("public key error")

// 解析公钥
pubInterface, err :&＃61; x509.ParsePKIXPublicKey(block.Bytes) // 目前的数字证书一般都是基于ITU&＃xff08;国际电信联盟&＃xff09;制定的X.509标准
if err !&＃61; nil
return nil, err

// 类型断言
pub :&＃61; pubInterface.(*rsa.PublicKey)
// 加密
return rsa.EncryptPKCS1v15(rand.Reader, pub, origData)

// RSA解密
func RsaDecrypt(ciphertext []byte) ([]byte, error)
// 解密
block, _ :&＃61; pem.Decode(privateKey)
if block &＃61;&＃61; nil
return nil, errors.New("private key error!")

// 解析PKCS1格式的私钥
priv, err :&＃61; x509.ParsePKCS1PrivateKey(block.Bytes)
if err !&＃61; nil
return nil, err

// 解密
return rsa.DecryptPKCS1v15(rand.Reader, priv, ciphertext)



ECC&＃xff08;Elliptic Curve Cryptography&＃xff09;椭圆曲线加密算法&＃xff0c;相比RSA&＃xff0c;ECC可以使用更短的密钥&＃xff0c;来实现与RSA相当或更高的安全
定义了椭圆曲线上的加法和二倍运算&＃xff0c;椭圆曲线依赖的数学难题是&＃xff1a;k为正整数&＃xff0c;P是椭圆曲线上的点&＃xff08;称为基点&＃xff09;, k*P&＃61;Q , 已知Q和P&＃xff0c;很难计算出k

func genPrivateKey() (*ecies.PrivateKey, error)
pubkeyCurve :&＃61; elliptic.P256() // 初始化椭圆曲线
// 随机挑选基点,生成私钥
p, err :&＃61; ecdsa.GenerateKey(pubkeyCurve, rand.Reader) // 用golang标准库生成公私钥对
if err !&＃61; nil
return nil, err
else
return ecies.ImportECDSA(p), nil // 转换成以太坊的公私钥对


// ECCEncrypt 椭圆曲线加密
func ECCEncrypt(plain string, pubKey *ecies.PublicKey) ([]byte, error)
src :&＃61; []byte(plain)
return ecies.Encrypt(rand.Reader, pubKey, src, nil, nil)

// ECCDecrypt 椭圆曲线解密
func ECCDecrypt(cipher []byte, prvKey *ecies.PrivateKey) (string, error)
if src, err :&＃61; prvKey.Decrypt(cipher, nil, nil); err !&＃61; nil
return "", err
else
return string(src), nil




3. 哈希算法

哈希函数的基本特征&＃xff1a;

• 输入可以是任意长度
• 输出是固定长度
• 根据输入很容易计算出输出
• 根据输出很难计算出输入&＃xff08;几乎不可能&＃xff09;
• 两个不同的输入几乎不可能得到相同的输出

SHA&＃xff08;Secure Hash Algorithm&＃xff09; 安全散列算法&＃xff0c;是一系列密码散列函数&＃xff0c;有多个不同安全等级的版本&＃xff1a;SHA-1,SHA-224,SHA-256,SHA-384,SHA-512&＃xff0c;其作用是防伪装&＃xff0c;防窜扰&＃xff0c;保证信息的合法性和完整性
sha-1算法大致过程&＃xff1a;

• 填充&＃xff0c;使得数据长度对512求余的结果为448
• 在信息摘要后面附加64bit&＃xff0c;表示原始信息摘要的长度
• 初始化h0到h4&＃xff0c;每个h都是32位
• h0到h4历经80轮复杂的变换
• 把h0到h4拼接起来&＃xff0c;构成160位&＃xff0c;返回

func Sha1(data string) string
sha1 :&＃61; sha1.New()
sha1.Write([]byte(data))
return hex.EncodeToString(sha1.Sum(nil))



MD5&＃xff08;Message-Digest Algorithm 5&＃xff09;信息-摘要算法5&＃xff0c;算法流程跟SHA-1大体相似&＃xff0c;MD5的输出是128位&＃xff0c;比SHA-1短了32位&＃xff0c;MD5相对易受密码分析的攻击&＃xff0c;但运算速度比SHA-1快

func Md5(data string) string
md5 :&＃61; md5.New()
md5.Write([]byte(data))
return hex.EncodeToString(md5.Sum(nil))



哈希函数的应用场景

• 用户密码的存储
• 文件上传/下载完整性校验
• mysql大字段的快速对比

数字签名

比特币中验证交易记录的真实性用的就是数字签名&＃xff0c;先hash再用私钥加密的原因是&＃xff1a;非对称加密计算量比较大&＃xff0c;先hash可以把原始数据转一条很短的信息&＃xff0c;提高计算效率

1. 链表

链表的一个应用案例&＃xff0c;LRU&＃xff08;Least Recently Used&＃xff0c;最近最少使用&＃xff09;缓存淘汰的总体思路&＃xff1a;缓存的key放到链表中&＃xff0c;头部的元素表示最近刚使用

• 如果命中缓存&＃xff0c;从链表中找到对应的key&＃xff0c;移到链表头部
• 如果没命中缓存&＃xff1a;
  
  • 如果缓存容量没超&＃xff0c;放入缓存&＃xff0c;并把key放到链表头部
  • 如果超出缓存容量&＃xff0c;删除链表尾部元素&＃xff0c;再把key放到链表头部

ring的应用&＃xff1a;基于滑动窗口的统计&＃xff0c;比如最近100次接口调用的平均耗时、最近10笔订单的平均值、最近30个交易日股票的最高点&＃xff1b;ring的容量即为滑动窗口的大小&＃xff0c;把待观察变量按时间顺序不停地写入ring即可

package main
import (
"container/ring"
"fmt"
)
func TraverseRing(ring *ring.Ring)
// 通过Do()来遍历ring&＃xff0c;内部实际上调用了Next()而非Prev()
ring.Do(func(i interface)
fmt.Printf("%v ", i)
)
fmt.Println()

func main()
ring :&＃61; ring.New(5) // 必须指定长度&＃xff0c;各元素被初始化为nil
ring2 :&＃61; ring.Prev()
for i :&＃61; 0; i < 3; i&＃43;&＃43;
ring.Value &＃61; i
ring &＃61; ring.Next()

for i :&＃61; 0; i < 3; i&＃43;&＃43;
ring2.Value &＃61; i
ring2 &＃61; ring2.Prev()

TraverseRing(ring)
TraverseRing(ring2) // ring和ring2当前所在的指针位置不同&＃xff0c;所以遍历出来的顺序也不同



2. 栈

栈是一种先进后出的数据结构&＃xff0c;push把元素压入栈底&＃xff0c;pop弹出栈顶的元素&＃xff0c;编程语言的编译系统也用到了栈的思想

go自带的List已经包含了栈的功能&＃xff0c;这里实现一个线程安全的栈

type (
node struct
value interface
prev *node

MyStack struct
top *node
length int
lock *sync.RWMutex

)
func NewMyStack() *MyStack
return &MyStacknil, 0, &sync.RWMutex

func (stack *MyStack) Push(value interface)
stack.lock.Lock()
defer stack.lock.Unlock()
n :&＃61; &nodevalue, stack.top
stack.top &＃61; n
stack.length&＃43;&＃43;

func (stack *MyStack) Pop() interface
stack.lock.Lock()
defer stack.lock.Unlock()
if stack.length &＃61;&＃61; 0
return nil

n :&＃61; stack.top
stack.top &＃61; n.prev
stack.length--
return n.value

func (stack *MyStack) Peak() interface
stack.lock.RLock()
defer stack.lock.RUnlock()
if stack.length &＃61;&＃61; 0
return nil

return stack.top.value

func (stack *MyStack) Len() int
return stack.length

func (stack *MyStack) Empty() bool
return stack.Len() &＃61;&＃61; 0



3. 堆

堆是一棵二叉树&＃xff0c;大根堆即任意节点的值都大于等于其子节点&＃xff0c;反之为小根堆
用数组来表示堆&＃xff0c;下标为 i 的结点的父结点下标为(i-1)/2&＃xff0c;其左右子结点分别为 (2i &＃43; 1)、(2i &＃43; 2)

构建堆

package main
import "fmt"
// AdjustTraingle 如果只是修改slice里的元素&＃xff0c;不需要传slice的指针&＃xff1b;如果要往slice里append或让slice指向新的子切片&＃xff0c;则需要传slice指针
func AdjustTraingle(arr []int, parent int)
left :&＃61; 2 * parent &＃43; 1
if left >&＃61; len(arr)
return

right :&＃61; 2 * parent &＃43; 2
minIndex :&＃61; parent
minValue :&＃61; arr[minIndex]
if arr[left] < minValue
minValue &＃61; arr[left]
minIndex &＃61; left

if right < len(arr)
if arr[right] < minValue
minValue &＃61; arr[right]
minIndex &＃61; right


if minIndex !&＃61; parent
arr[minIndex], arr[parent] &＃61; arr[parent], arr[minIndex]
// 递归&＃xff0c;每当有元素调整下来时&＃xff0c;要对以它为父节点的三角形区域进行调整
AdjustTraingle(arr, minIndex)


func ReverseAdjust(arr []int)
n :&＃61; len(arr)
if n <&＃61; 1
return

lastIndex :&＃61; n / 2 * 2
fmt.Println(lastIndex)
// 逆序检查每一个三角形区域
for i :&＃61; lastIndex; i > 0; i -&＃61; 2
right :&＃61; i
parent :&＃61; (right - 1) / 2
fmt.Println(parent)
AdjustTraingle(arr, parent)


func buildHeap()
arr :&＃61; []int62, 40, 20, 30, 15, 10, 49
ReverseAdjust(arr)
fmt.Println(arr)



每当有元素调整下来时&＃xff0c;要对以它为父节点的三角形区域进行调整

插入元素

删除堆顶

下面讲几个堆的应用
堆排序&＃xff1a;

• 构建堆O(N)
• 不断地删除堆顶O(NlogN)

求集合中最大的K个元素&＃xff1a;

• 用集合的前K个元素构建小根堆
• 逐一遍历集合的其他元素&＃xff0c;如果比堆顶小直接丢弃&＃xff1b;否则替换掉堆顶&＃xff0c;然后向下调整堆

把超时的元素从缓存中删除&＃xff1a;

• 按key的到期时间把key插入小根堆中
• 周期扫描堆顶元素&＃xff0c;如果它的到期时间早于当前时刻&＃xff0c;则从堆和缓存中删除&＃xff0c;然后向下调整堆

Golang中的container/heap实现了小根堆&＃xff0c;但需要自己定义一个类&＃xff0c;实现以下接口&＃xff1a;

• Len() int
• Less(i, j int) bool
• Swap(i, j int)
• Push(x interface)
• Pop() x interface

type Item struct
Value string
priority int // 优先级&＃xff0c;数字越大&＃xff0c;优先级越高

type PriorityQueue []*Item
func (pq PriorityQueue) Len() int
return len(pq)

func (pq PriorityQueue) Less(i, j int) bool
// Golang默认提供的是小根堆&＃xff0c;而优先队列是大根堆&＃xff0c;所以这里要反着定义Less
return pq[i].priority > pq[j].priority

func (pq PriorityQueue) Swap(i, j int)
pq[i], pq[j] &＃61; pq[j], pq[i]

// 往slice里append&＃xff0c;需要传slice指针
func (pq *PriorityQueue) Push(x interface)
item :&＃61; x.(*Item)
*pq &＃61; append(*pq, item)

// 让slice指向新的子切片&＃xff0c;需要传slice指针
func (pq *PriorityQueue) Pop() interface
old :&＃61; *pq
n :&＃61; len(old)
item :&＃61; old[n-1] // 数组最后一个元素
*pq &＃61; old[0 : n-1] // 去掉最一个元素
return item



4. Trie树

Trie树又叫字典权
现有term集合&＃xff1a;分散&＃xff0c;分散精力&＃xff0c;分散投资&＃xff0c;分布式&＃xff0c;工程&＃xff0c;工程师&＃xff0c;把它们放到Trie树里如下图&＃xff1a;

Trie树的根节点是总入口&＃xff0c;不存储字符&＃xff1b;对于英文&＃xff0c;第个节点有26个子节点&＃xff0c;子节点可以存到数组里&＃xff1b;中文由于汉字很多&＃xff0c;用数组存子节点太浪费内存&＃xff0c;可以用map存子节点&＃xff1b;从根节点到叶节点的完整路径是一个term&＃xff0c;从根节点到某个中间节点也可能是一个term&＃xff0c;即一个term可能是另一个term的前缀&＃xff1b;上图中红圈表示从根节点到本节点是一个完整的term

package main
import "fmt"
type TrieNode struct
Word rune // 当前节点存储的字符。byte只能表示英文字符&＃xff0c;rune可以表示任意字符
Children map[rune]*TrieNode // 孩子节点&＃xff0c;用一个map存储
Term string

type TrieTree struct
root *TrieNode

// add 把words[beginIndex:]插入到Trie树中
func (node *TrieNode) add(words []rune, term string, beginIndex int)
// words已经遍历完了
if beginIndex >&＃61; len(words)
node.Term &＃61; term
return

if node.Children &＃61;&＃61; nil
node.Children &＃61; make(map[rune]*TrieNode)

word :&＃61; words[beginIndex] // 把这个word放到node的子节点中
if child, exists :&＃61; node.Children[word]; !exists
newNode :&＃61; &TrieNodeWord: word
node.Children[word] &＃61; newNode
newNode.add(words, term, beginIndex&＃43;1) // 递归
else
child. var cpro_id = "u6885494";